package 动态规划.贪心算法;

/**
 * @description:
 * @author: ywk
 * @date: 2021-01-12
 */
public class 跳跃的最小次数 {
    public static int[] memo;

    //1.动态规划
    public static int minJump(int[] arr) {
        int n = arr.length;
        memo = new int[arr.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = n;
        }
        return dp(arr, 0);
    }

    private static int dp(int[] nums, int p) {
        int n = nums.length;
        if (p >= n - 1) {
            return 0;
        }
        if (memo[p] != n) {
            return memo[p];
        }
        int steps = nums[p];
        for (int i = 1; i <= steps; i++) {
            int subProblem = dp(nums, p + i);
            memo[p] = Math.min(memo[p], subProblem + 1);
        }
        return memo[p];
    }

    //2.贪心算法
    static int jump(int[] nums) {

        int n = nums.length;
        int end = 0, farthest = 0;
        int jumps = 0;
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.max(nums[i] + i, farthest);
            if (end == i) {
                jumps++;
                end = farthest;
            }
        }
        return jumps;
    }

    public static void main(String[] args) {
        System.out.println(minJump(new int[]{2, 3, 1, 1, 4}));
        System.out.println(jump(new int[]{2, 3, 1, 1, 4}));

    }
}
